# 4.1.7 堆排序

// 1) 初始堆：将原始数组调整成大根堆的方法——筛选算法:子节点都比父节点小
// 2) 堆排序： 每次将堆顶元素与数组最后面的且没有被置换的元素互换。
// 参考代码： http://bubkoo.com/2014/01/14/sort-algorithm/heap-sort/
function sort8(array) {
  var result = array.slice(0);

  function swap(array, i, j) {
    var temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }

  function maxHeapify(array, index, heapSize) {
    var iMax, iLeft, iRight;
    while (true) {
      iMax = index;
      iLeft = 2 * index + 1;
      iRight = 2 * (index + 1);

      if (iLeft < heapSize && array[index] < array[iLeft]) {
        iMax = iLeft;
      }

      if (iRight < heapSize && array[iMax] < array[iRight]) {
        iMax = iRight;
      }

      if (iMax != index) {
        swap(array, iMax, index);
        index = iMax;
      } else {
        break;
      }
    }
  }

  function buildMaxHeap(array) {
    var i, iParent = Math.floor(array.length / 2) - 1;

    for (i = iParent; i >= 0; i--) {
      maxHeapify(array, i, array.length);
    }
  }

  function sort(array) {
    buildMaxHeap(array);

    for (var i = array.length - 1; i > 0; i--) {
      swap(array, 0, i);
      maxHeapify(array, 0, i);
    }
    return array;
  }

  return sort(result);
}

* 排序思路：（降序）
 * 将堆根保存于尾部，并对剩余序列调用调整函数，调整完成后，再将最大跟保存于尾部-1（-1，-2，...，-i），
 * 再对剩余序列进行调整，反复进行该过程，直至排序完成。
 */

/* 将最大的元素调整到堆顶*/
function AdjustHeap(arr, pos, len){
    var swap = arr[pos];      //保存当前节点
    var child = pos * 2 + 1;  //定位到当前节点的左边的子节点
    while(child < len){       //递归遍历所有的子节点
        //判断当前节点是否有右节点，若右节点较大，就采用右节点和当前节点进行比较
        if(child + 1 < len && arr[child] < arr[child + 1]){
            child += 1;
        }
        //比较当前节点和最大的子节点，小于就交换，交换后将当前节点定位到子节点上
        if(arr[pos] < arr[child]){
            arr[pos] = arr[child];
            pos = child;
            child = pos * 2 + 1;
        }
        else{
            break;
        }
        arr[pos] = swap;
    }
}

/* 构建堆：
 * 满足：树中任一非叶子结点的关键字均不大于（或不小于）其左右孩子结点的关键字。
 * 实现：从最后一个拥有子节点的节点开始，将该节点和其他节点进行比较，将最大的数交换给该节点，
 *      交换后再依次向前节点进行相同的交换处理，直到构建出大顶堆。
 */
function BuildHeap(arr){
  for(var i=arr.length/2; i>=0; i--){  //构建打顶堆
      AdjustHeap(arr, i, arr.length);
  }
}

/*堆排序算法*/
function HeapSort(arr){
    BuildHeap(arr); //构建堆
    for(var i=arr.length-1; i>0; i--){   //从数组的尾部进行调整
        var swap = arr[i];  //堆顶永远是最大的元素,将堆顶和尾部元素交换，最大元素就保存在尾部，并且不参与后面的调整
        arr[i] = arr[0];
        arr[0] = swap;
        AdjustHeap(arr, 0, i); //将最大的元素进行调整，将最大的元素调整到堆顶
    }
}

var arr = [46,12,33,72,68,19,80,33];
console.log('before: ' + arr);
HeapSort(arr);
console.log(' after: ' + arr);
--------------------- 
作者：Cynthia（小英子） 
来源：CSDN 
原文：https://blog.csdn.net/ganyingxie123456/article/details/69053478 
版权声明：本文为博主原创文章，转载请附上博文链接！